package leetcode_100;

/**
 *@author 周杨
 *ReverseLinkedListII_92 按照区间旋转一个链表
 *describe:考虑好从第一个节点就旋转的情况 AC 98%
 *2018年5月18日 下午7:37:20
 */
public class ReverseLinkedListII_92 {
	static class ListNode{
		int val;
		ListNode next;
		ListNode(int x) { val = x; }
	}
	ListNode reverseHead;
	ListNode reverseTail;
	ListNode pre;
	ListNode tail;
	public static void main(String[] args) {
		ReverseLinkedListII_92 test=new ReverseLinkedListII_92();
		ListNode a=new ListNode(1);
		a.next=new ListNode(2);
		a.next.next=new ListNode(3);
		a.next.next.next=new ListNode(4);
		a.next.next.next.next=new ListNode(5);
		ListNode result=test.reverseBetween(a, 1, 4);

	}
	
	public ListNode reverseBetween(ListNode head, int m, int n) {
		if(head==null||head.next==null)
			return head;
		if(n>m+1) {
	        this.pre=head;
	        for(int i=2;i<m;++i) {
	        	pre=pre.next;//找旋转链表的前端
	        }
	        if(m!=1) {
	        	reverse(pre.next, n-m+1);
	        	pre.next=this.reverseHead;
	        }
	        else
	        	reverse(head, n-m+1);
	        return m==1?this.reverseHead:head;
		}
		return head;  
    }
	
	public void reverse(ListNode head,int len) {
		reverseTail=head;
		reverseHead=head;
		ListNode run=head.next;
		--len;
		while(len>0) {
			this.tail=run.next;
			ListNode now=run;
			run=run.next;
			now.next=reverseHead;
			reverseHead=now;
			--len;
		}
		reverseTail.next=tail;
	}

}
